The Block of
the string S at position i is the largest
substring S that starts at position i and matches a prefix of S. The length of
the block at position 0 is considered to be zero.
Find the lengths
of the blocks of string S for all positions.
Input. One string S (|S| ≤ 106).
Output. Print a single line
containing the lengths of the blocks of string S for all positions.
|
Sample
input |
Sample
output |
|
abaabaab |
0 0 1 5 0 1 2 0 |
strings – z-function
Algorithm analysis
Ñompute the z-function for
the string S and store its values in the array v. Print the z-function
values for all positions i (0 ≤ i < n).
The input string s contains no more than 106 characters. The
z-function of the string s is stored in the vector v.
vector<int> v;
string s;
The z function computes and returns the z-function for the string s.
vector<int> z(string s)
{
int i, l, r, len = s.size();
vector<int>
z(len, 0);
l = 0, r = 0;
for (i = 1; i < len;
i++)
{
if (i
<= r) z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] <
len && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] - 1
> r)
{
l = i;
r = i + z[i] - 1;
}
}
return z;
}
The main part of the
program. Read the input string s.
getline(cin,s);
Compute the z-function.
v = z(s);
Print the z-function
values for all positions of the input string.
for (i = 0; i < v.size(); i++)
printf("%d ", v[i]);
printf("\n");